import java.util.ArrayList;
import java.util.List;

/**
 * 哈夫曼树类
 * 
 * @author yangmqglobe
 *
 */
class HuffmanTree {
	private HuffmanNode[] huffmanNodes = null;// 节点数组
	private int leafNodeNum;// 叶子节点数

	/**
	 * 获得哈夫曼树的根节点
	 * 
	 * @return 哈夫曼树根节点
	 */
	public HuffmanNode getRoot() {
		return huffmanNodes[huffmanNodes.length - 1];
	}

	/**
	 * 创建哈夫曼编码表
	 * 
	 * @return 哈夫曼编码表数组
	 */
	public String[] createHuffCodes() {
		String[] huffCodes = new String[leafNodeNum];
		for (int i = 0; i < leafNodeNum; i++) {
			List<Integer> codes = new ArrayList<Integer>();
			HuffmanNode c = huffmanNodes[i];
			HuffmanNode p = c.getParent();
			while (p != null) {
				if (p.getLchild().equals(c)) {
					codes.add(0);
				} else {
					codes.add(1);
				}
				c = p;
				p = p.getParent();
			}
			huffCodes[i] = "";
			for (int j = codes.size() - 1; j >= 0; j--) {
				huffCodes[i] += codes.get(j);
			}
		}
		return huffCodes;
	}

	/**
	 * 构造方法
	 * 
	 * @param weights
	 *            权值数组
	 */
	public HuffmanTree(int[] weights) {
		int n = weights.length;
		this.leafNodeNum = n;
		int m = n * 2 - 1;
		huffmanNodes = new HuffmanNode[m];
		// 插入所有的叶子节点
		for (int i = 0; i < n; i++) {
			huffmanNodes[i] = new HuffmanNode(weights[i]);
		}
		// 构造其他的节点
		for (int i = n; i < m; i++) {
			HuffmanNode min1 = selectMin(i - 1);
			min1.markFlag();
			HuffmanNode min2 = selectMin(i - 1);
			min2.markFlag();
			int weight = min1.getWeight() + min2.getWeight();
			huffmanNodes[i] = new HuffmanNode(weight);
			min1.setParent(huffmanNodes[i]);
			min2.setParent(huffmanNodes[i]);
			huffmanNodes[i].setLchild(min1);
			huffmanNodes[i].setRchild(min2);
		}
	}

	/**
	 * 选择权值最小的未进树节点
	 * 
	 * @param end
	 * @return
	 */
	private HuffmanNode selectMin(int end) {
		HuffmanNode min = huffmanNodes[end];
		// 排除已进树节点
		while (min.getFlag()) {
			min = huffmanNodes[end--];
		}
		// 寻找权值最小的节点
		for (int i = 0; i < end; i++) {
			HuffmanNode p = huffmanNodes[i];
			if (!p.getFlag() && p.getWeight() < min.getWeight()) {
				min = p;
			}
		}
		return min;
	}
}
